#include <iostream>
#include <vector>
#include <stack>

using namespace std;
// 84. 柱状图中最大的矩形
// 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
// 求在该柱状图中，能够勾勒出来的矩形的最大面积。

class Solution {
public:
    int largestRectangleArea(vector<int>& heights) {
        int ans = 0;
        heights.push_back(0);   // 保证最后栈被弹空
        for(int height : heights) {
            int accumulatedWidth = 0;   // 累加的宽度
            // 栈顶（之前）高度 >= 当前高度，单调性破坏，确定了栈顶高度的扩展范围，需要删除栈顶
            while(!s.empty() && s.top().height >= height) {
                accumulatedWidth += s.top().width;
                ans = max(ans, s.top().height * accumulatedWidth);
                s.pop();
            }
            s.push({accumulatedWidth+1,height});
        }
        return ans;
    }

private:
    struct Rect {
        int width;
        int height;
    };
    stack<Rect> s;  // 定义一个单调栈
};

int main() {
    vector<int> heights1({2,1,5,6,2,3});
    std::cout << Solution().largestRectangleArea(heights1) << std::endl;    // 10
    vector<int> heights2({2,4});
    std::cout << Solution().largestRectangleArea(heights2) << std::endl;    // 4
    return 0;
}
